package 解数独;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 解数独（困难）,这个是双递归，，其余都是单层for循环就可以解决问题
 * @date 2022/11/19 17:17
 */
public class Demo37 {
    public void solveSudoku(char[][] board) {
        backTrack(board);
    }

    private boolean backTrack(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]=='.'){
                    //遍历1-9，看看这个位置可以放那个数字
                    for (char k = '1'; k <='9' ; k++) {
                        if(isVaild(k,i,j,board)){
                            board[i][j]=k;
                            if (backTrack(board)){ // 如果找到合适一组立刻返回
                                return true;
                            }
                            //回溯
                            board[i][j]='.';
                        }
                    }
                    //1-9都放不了，直接返回
                    return false;
                }
            }
        }
        return true;

    }

    private boolean isVaild(char k, int row, int col, char[][] board) {
        //校验行
        for (int i = 0; i < board.length; i++) {
            if(board[i][col]==k){
                return false;
            }
        }
        //校验列
        for (int j = 0; j < board[0].length; j++) {
            if(board[row][j]==k){
                return false;
            }
        }
        //校验小方格
        int high=(row/3) *3;
        int with=(col/3) *3;
        for (int i = high; i <high+3 ; i++) {
            for (int j = with; j < with+3; j++) {
                if(board[i][j]==k){
                    return false;
                }
            }
        }
        return true;
    }

}
